package leetcode_301_400;

import java.time.YearMonth;
import java.util.*;

public class LeeCode_347 {
    public static void main(String[] args) {
//        System.out.println(Arrays.toString(topKFrequent2(new int[]{1, 1, 1, 2, 2, 3}, 2)));
        System.out.println(Arrays.toString(topKFrequent2(new int[]{4,1,-1,-1,2,2,3}, 2)));
    }
    private static int[] topKFrequent2(int[] nums, int k) {
        Map<Integer, Integer> map = getMap(nums);
        Set<Integer> keys = map.keySet();
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        for (Integer key : keys) {
            int[] tmp = new int[]{key, map.get(key)};
            if (queue.size() < k){
                queue.add(tmp);
            }else {
                int[] peek = queue.peek();
                if (peek[1] < tmp[1]){
                    queue.poll();
                    queue.add(tmp);
                }
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = queue.poll()[0];
        }
        return ans;
    }

    private static int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> map = getMap(nums);
        Set<Integer> keys = map.keySet();
        int i = 0;
        int[][] arr = new int[keys.size()][2];
        for (Integer key : keys) {
            int[] son = new int[]{key, map.get(key)};
            arr[i] = son;
            i++;
        }
        Arrays.sort(arr, (o1, o2) -> o2[1] - o1[1]);
        int[] ans = new int[k];
        for (int j = 0; j < ans.length; j++) {
            ans[j] = arr[j][0];
        }
        return ans;
    }

    private static Map<Integer, Integer> getMap(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        return map;
    }
}
